using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace Rogue
{
    public class LightCaster
    {

        // The data for each cell for light-casting
        public class RayData
        {
            public int xLoc;    // position in lightspace
            public int yLoc;

            public float angleToCenter;   // all the angles are measured from the light

            public float maxAng;   // the min and max angles of the shadow that covers us.
            public float minAng;
            public bool m_IsCarryingShadow = false;   // true once the min/max angles are set

            public bool m_IsVisible = true;


            public RayData(int a_x, int a_y)
            {
                xLoc = a_x;
                yLoc = a_y;
                angleToCenter = (float)Math.Atan2(yLoc, xLoc);
                minAng = maxAng = angleToCenter;
            }

            static public float OneSquaresAngle(int x, int y)
            {
                float dist = (float)Math.Sqrt(x*x + y*y);
                return 1.0f / (dist + 0.3f); // a stupid approximation. The correct one is doing arctans of angles...
            }

            public float OneSquaresAngle()
            {
                return OneSquaresAngle(xLoc, yLoc);
            }

            public bool IsObscuredBy(float a_minAngle, float a_maxAngle)
            {
                float wrappedToCenter = MatchRange(angleToCenter, a_minAngle);   // handle 2pi wraparound

                return a_minAngle < wrappedToCenter && wrappedToCenter < a_maxAngle;
            }

            // does the shadow from another cell cover us?
            public bool IsObscuredBy(RayData a_Other)
            {
                if (!a_Other.m_IsCarryingShadow)
                    return false;

                // it has to cover most/all of us, not just the exact middle spot
                float toCorners = OneSquaresAngle() * 0.5f;
                return IsObscuredBy(a_Other.minAng + toCorners, a_Other.maxAng - toCorners);    // shrink the angles a bit
            }

        }


        private GameMap m_Map; // holds obstruction data

        private Point m_Origin;
        public Point Origin // the ray caster's worldspace position
        {
            get { return m_Origin; }

            set
            {
                m_Origin = new Point(Math.Min(m_Map.Bounds().Width-1, Math.Max(0, value.X)), 
                                    Math.Min(m_Map.Bounds().Height-1, Math.Max(0, value.Y)));
            }
        }

        private float m_Radius;
        public float Radius
        { 
            get { return m_Radius; }
            set { m_Radius = value; }
        }

        public Queue<RayData> perimeter; // rays currently on the search frontier
        public Dictionary<Point, RayData> results; // worldspace coords -> raycast info


        public LightCaster(GameMap world)
        {
            this.m_Map = world;
            m_Origin = Point.Zero;

            this.perimeter = new Queue<RayData>();
            this.results = new Dictionary<Point, RayData>();
        }

        public void Reset()
        {
            results = null;
            results = new Dictionary<Point, RayData>();
            perimeter = null;
            perimeter = new Queue<RayData>();
        }

        // If it returns null, the cell was never explored (and so isn't visible / is shadowed)
        public RayData GetRay(Point a_Worldspace)
        {
            RayData newRay = null;
            results.TryGetValue(a_Worldspace, out newRay);
            return newRay;
        }

        public bool IsVisible(Point a_Worldspace)
        {
            RayData newRay = null;
            results.TryGetValue(a_Worldspace, out newRay);
            if (newRay == null)
                return false;

            return newRay.m_IsVisible;
        }

        public RayData GetRayLightspace(Point a_LightSpace)
        {
            return GetRay(new Point(Origin.X + a_LightSpace.X, Origin.Y + a_LightSpace.Y));
        }

        public void castRays()
        {
            foreach (RayData r in castRaysStep())
                ;
        }

        // Does a breadth-first search of the world starting at the light origin, 
        // maintaining (and pruning) a work queue until there's no work left to do.
        public IEnumerable<RayData> castRaysStep()
        {
            RayData firstRay = new RayData(0, 0);
            results[new Point(Origin.X, Origin.Y)] = firstRay;
            expandPerimeterFrom(firstRay);

            // since we are traversing breadth-first, all inputs are guaranteed 
            // to be added to current data by the time it is processed.

            while (perimeter.Count > 0)
            {
                RayData currentRay = perimeter.Dequeue();

                mergeInputs(currentRay);        // might set IsVisible to false

                float squaredDist = currentRay.xLoc * currentRay.xLoc + currentRay.yLoc * currentRay.yLoc;
                if (currentRay.m_IsVisible && squaredDist < m_Radius*m_Radius)
                {
                    expandPerimeterFrom(currentRay);
                }

                yield return currentRay;
            }
        }

        public Point GetXInputCoords(RayData a_Ray)
        {
            return new Point(a_Ray.xLoc - Math.Sign(a_Ray.xLoc), a_Ray.yLoc);
        }

        public Point GetYInputCoords(RayData a_Ray)
        {
            return new Point(a_Ray.xLoc, a_Ray.yLoc - Math.Sign(a_Ray.yLoc));
        }

        // Find the cell in the X direction that would influence this cell (which is the neighboring cell towards the origin).
        // If it doesn't exist, the cell's ignored (ie treat it like it's shadowed)
        public RayData GetXInput(RayData a_Ray)
        {
            if (a_Ray.xLoc == 0)
                return null;

            return GetRayLightspace(GetXInputCoords(a_Ray));
        }

        // and the Y direction
        public RayData GetYInput(RayData a_Ray)
        {
            if (a_Ray.yLoc == 0)
                return null;

            return GetRayLightspace(GetYInputCoords(a_Ray));
        }



        // Bring two floats to within PI (half a rot) of each other, so it's easier to compare them.
        static float MatchRange(float a_ChangeThis, float a_ToMatchThis)
        {
            if (a_ChangeThis - a_ToMatchThis > (float)Math.PI)
                a_ChangeThis -= 2.0f * (float)Math.PI;
            else if (a_ToMatchThis - a_ChangeThis > (float)Math.PI)
                a_ChangeThis += 2.0f * (float)Math.PI;

            return a_ChangeThis;
        }

        // after matching the range of two angles, which of them is further clockwise?
        static float AngleMin(float a, float b)
        {
            a = MatchRange(a, b);
            if (a < b)
                return a;
            else
                return b;
        }

        static float AngleMax(float a, float b) // and ccw
        {
            a = MatchRange(a, b);
            if (a > b)
                return a;
            else
                return b;
        }

        // expand our min/max angles to encompass shadow data from our neighbors
        private void InheritShadowFromNeighbor(RayData newRay, RayData oldRay)
        {
            if (oldRay == null || (oldRay.xLoc == 0 && oldRay.yLoc == 0) || !oldRay.m_IsCarryingShadow)
                return;

            // only propogate shadow info if it's near to covering us
            float maxAngleDiff = newRay.OneSquaresAngle(); // how far away from our angle we're willing to hold shadow data
            float fatterMax = oldRay.maxAng + maxAngleDiff;
            float fatterMin = oldRay.minAng - maxAngleDiff;
            float wrappedAngToCenter = MatchRange(newRay.angleToCenter, fatterMax);
            if (wrappedAngToCenter < fatterMin || wrappedAngToCenter > fatterMax)     // it's too far from where we are, ditch it.
                return;

            // propogate shadow info
            if (!newRay.m_IsCarryingShadow)
            {
                newRay.minAng = oldRay.minAng;
                newRay.maxAng = oldRay.maxAng;
                newRay.m_IsCarryingShadow = true;
            }
            else
            {
                newRay.minAng = AngleMin(newRay.minAng, oldRay.minAng);
                newRay.maxAng = AngleMax(newRay.maxAng, oldRay.maxAng);
            }
        }

        // Once all inputs are known to be assigned, mergeInputs performs the key 
        // task of populating the new ray with the correct data. 
        // Returns whether we should expand the perimeter (ie. give the cell children)
        private void mergeInputs(RayData a_newRay)
        {
            RayData xInput = GetXInput(a_newRay);
            RayData yInput = GetYInput(a_newRay);

            // inherit shadow angles from our parents
            InheritShadowFromNeighbor(a_newRay, xInput);
            InheritShadowFromNeighbor(a_newRay, yInput);

            // Is this an obstruction? it will cast a shadow to the rest of the map
            if (m_Map.BlocksLight(Origin.X + a_newRay.xLoc,
                                    Origin.Y + a_newRay.yLoc))
            {
                // arbitrary angles for shadows that come out of a square - I picked the angles to the middles of the edges
                // (making the shadow-caster shape for a tile a diamond). They overlap a tiny bit for precision's sake..
                const float diamondWidth = 0.51f;
                float angleTop =    (float)Math.Atan2(  (double)(a_newRay.yLoc - diamondWidth), (double)a_newRay.xLoc);
                float angleLeft =   (float)Math.Atan2(  (double)a_newRay.yLoc,                  (double)a_newRay.xLoc - diamondWidth);
                float angleBottom = (float)Math.Atan2(  (double)a_newRay.yLoc + diamondWidth,   (double)a_newRay.xLoc);
                float angleRight =  (float)Math.Atan2(  (double)a_newRay.yLoc,                  (double)a_newRay.xLoc + diamondWidth);

                a_newRay.m_IsCarryingShadow = true;

                // expand our min/max ranges to include those angles
                a_newRay.minAng = AngleMin(a_newRay.minAng, AngleMin(angleRight, 
                                AngleMin(angleBottom, AngleMin(angleTop, angleLeft))));
                
                a_newRay.maxAng = AngleMax(a_newRay.maxAng, AngleMax(angleRight, 
                                AngleMax(angleBottom, AngleMax(angleTop, angleLeft))));
            }



            // axis-aligned and in shadow?
            if (a_newRay.xLoc == 0 && a_newRay.yLoc != 0)       // on Y axis
            {
                if (a_newRay.IsObscuredBy(yInput))
                    a_newRay.m_IsVisible = false;
                return;
            }
            if (a_newRay.yLoc == 0 && a_newRay.xLoc != 0)  // axis aligned on X axis
            {
                if (a_newRay.IsObscuredBy(xInput))
                    a_newRay.m_IsVisible = false;

                return;
            }

            // a culled parent X? Treat it like a shadowcaster...
            float s_CulledCellShadowWidth = 0.45f;
            if (xInput == null)
            {
                Point xInputCoords = GetXInputCoords(a_newRay);
                float angleToXInput = (float)Math.Atan2(xInputCoords.Y, xInputCoords.X);
                float width = s_CulledCellShadowWidth * RayData.OneSquaresAngle(xInputCoords.X, xInputCoords.Y);
                if (a_newRay.IsObscuredBy(angleToXInput - width, angleToXInput + width))
                {
                    a_newRay.m_IsVisible = false;
                    return;
                }
            }

            if (yInput == null)     // culled parent Y, another shadowcaster
            {
                Point yInputCoords = GetYInputCoords(a_newRay);
                float angleToYInput = (float)Math.Atan2(yInputCoords.Y, yInputCoords.X);
                float width = s_CulledCellShadowWidth * RayData.OneSquaresAngle(yInputCoords.X, yInputCoords.Y);
                if (a_newRay.IsObscuredBy(angleToYInput - width, angleToYInput + width))
                {
                    a_newRay.m_IsVisible = false;
                    return;
                }
            }

            // shaded by (at least) one parent?
            if ((xInput != null && a_newRay.IsObscuredBy(xInput)) ||
                (yInput != null && a_newRay.IsObscuredBy(yInput)))
            {
                a_newRay.m_IsVisible = false;
                return;
            }

            return;
        }


        // Expands by the unit length in each component's current direction.
        // If a component has no direction, then it is expanded in both of its 
        // positive and negative directions.
        private void expandPerimeterFrom(RayData expanding)
        {
            // expand away from the origin
            if (expanding.xLoc >= 0)
                processRay(expanding.xLoc + 1, expanding.yLoc, expanding);
            if (expanding.xLoc <= 0)
                processRay(expanding.xLoc - 1, expanding.yLoc, expanding);
            if (expanding.yLoc >= 0)
                processRay(expanding.xLoc, expanding.yLoc + 1, expanding);
            if (expanding.yLoc <= 0)
                processRay(expanding.xLoc, expanding.yLoc - 1, expanding);
        }

        // Does bounds checking, marks obstructions, assigns inputs, and adds the 
        // ray to the perimeter if it is valid. Coordinates in light-space.
        private void processRay(int a_X, int a_Y, RayData a_ExpandingRay)
        {
            Point worldSpace = new Point(Origin.X + a_X, Origin.Y + a_Y);

            if (!m_Map.Bounds().Contains(worldSpace))
                return;

            // Since there are multiple inputs to each new ray, we need to check if 
            // the new ray has already been set up.
            RayData newRay = null;
            if (!results.TryGetValue(worldSpace, out newRay))
            {
                // It's not already set up (or ignored) - add it to the work queue and put it in the results table.
                newRay = new RayData(a_X, a_Y);
                perimeter.Enqueue(newRay);
                results[worldSpace] = newRay;
            }
        }

        
        // debug rendering...
        public void DebugDrawDelegate(GameMap a_Map, Rectangle a_MapArea, TerrainWindow a_TerrainWindow, Rectangle a_TerrainWindowArea)
        {
            for (int y = a_MapArea.Top; y < a_MapArea.Bottom; y++)
            {
                for (int x = a_MapArea.Left; x < a_MapArea.Right; x++)
                {
                    Point worldSpace = new Point(x, y);

                    RayData here = GetRay(worldSpace);

                    int windowX = x - a_Map.Camera.RenderableArea.Left;
                    int windowY = y - a_Map.Camera.RenderableArea.Top;

                    if (!a_TerrainWindowArea.Contains(new Point(windowX, windowY)))
                        continue;

                    Color color = Color.DarkGreen;   // not visible, not carrying shadow
                    if (here == null)
                        color = Color.DarkSlateGray;
                    else if (here.m_IsCarryingShadow)
                        color = Color.LightGreen;
                    else if (here.m_IsVisible)
                        color = Color.Yellow;

                    a_TerrainWindow.SetForegroundColor(windowX, windowY, color);
                }
            }

            foreach (RayData next in perimeter)
            {
                Point windowSpace = a_Map.Camera.CellToWindowSpace(new Point(next.xLoc + m_Origin.X, next.yLoc + m_Origin.Y));
                a_TerrainWindow.DrawCellOutline(windowSpace, Color.DarkMagenta);
            }

            if (perimeter.Count > 0)    // do the first one last, so it draws overtop
            {
                RayData next = perimeter.Peek();
                Point windowSpace = a_Map.Camera.CellToWindowSpace(new Point(next.xLoc + m_Origin.X, next.yLoc + m_Origin.Y));
                a_TerrainWindow.DrawCellOutline(windowSpace, Color.LightPink);

                string labelNext = string.Format("                      {0:0.00}", next.angleToCenter);
                LabelHelper.Instance.Add(labelNext, new Point(m_Origin.X + next.xLoc, m_Origin.Y + next.yLoc), "caster debug label next");


                RayData xInput = GetXInput(next);
                RayData yInput = GetYInput(next);

                if (xInput != null && xInput.m_IsCarryingShadow)
                {
                    string labelX = string.Format("xInput ({0:0.00}, {1:0.00})", xInput.minAng, xInput.maxAng);
                    LabelHelper.Instance.Add(labelX, new Point(m_Origin.X + xInput.xLoc, m_Origin.Y + xInput.yLoc), "caster debug label X");
                }
                else
                {
                    LabelHelper.Instance.Remove("caster debug label X");
                }

                if (yInput != null && yInput.m_IsCarryingShadow)
                {
                    string labelY = string.Format("yInput ({0:0.00}, {1:0.00})", yInput.minAng, yInput.maxAng);
                    LabelHelper.Instance.Add(labelY, new Point(m_Origin.X + yInput.xLoc, m_Origin.Y + yInput.yLoc), "caster debug label Y");
                }
                else
                {
                    LabelHelper.Instance.Remove("caster debug label Y");
                }
            }
        }

    }
}
